/* This program is based on a new string comparison metric called Greedy
   String Tiling (a more socially acceptable use for the acronym GST),
   and uses a modication of the Karp-Rabin string matching, called
   Running Karp-Rabin. These are described in the paper
	``Running Karp-Rabin Matching and Greedy String Tiling''
   which has been submitted to Software - Practice and Experience

   Unlike the tokenizers for YAP1 and YAP2, it is assumed that the
   alphabet of tokens are the integers from 0 to the cardinality of
   of the alphabet (minus 1), and the first integer in a file is
   the size of the string (small convenience, otherwise not significant).

   The top level of this program is taken from YAP2, written by Peter Burn, 1991

   Version 1.1 based on version 1.11.1.13 of algorithm
   Version 1.2 based on version 1.11.1.14 of algorithm (heap for storing
	matches replaced by list of lists; one list for each match-length)
   Version 1.3 based on version 1.11.1.15 of algorithm (some small performance
	fixes and fix to function rkr_gst - avoid loops caused by very_long_string

*/

#include <stdio.h>
#include <libgen.h>  /* for basename - compile with -lgen */


#define MAX_FILE_NAME 50	/* maximum length of file name */
#define MAX_NO_FILES  1500  /* maximum No. of submissions */
#define MAXFILE   10000	/* Maximum number of tokens in a file */
#define VOCAB_LENGTH   1000
#define MIN_STRING 3
#define MARK -1
#define KR_MULT 131	/* Multiplier used in Running KR (variant of Horners Rule) */
#define HASH_TABLE_SIZE  997

/* #define DEBUG 1 */	/* Remove comments to turn on debugging output */
/* #define DISPLAY_TILES 1 */    /* Removed comments to display tiles as they are created */

#define FALSE 0
#define TRUE 1

#define DOWN 0
#define UP 1

#define unmarked(x) (((x).value) > 0)
#define marked(x) (((x).value) < 0)

typedef  char  boolean;
typedef char filename[MAX_FILE_NAME];

typedef struct word_struct
{
    short value,	/* negated value implied part of tile */
	  prev,
	  next,		/* when part of tile, next points to start of opposing tile */
	  end;		/* when part of tile, points to end of current tile */
} word_struct;

/* The following data-structure store putative tiles prior to testing in markarrays
   The first is the list tiles of particular size. The second tile_spine_struct
   organizes a list of queues */
typedef struct tile_struct
{
    unsigned short start_patn, end_patn, start_text, end_text;
    struct tile_struct *chain,		/* used recovery/reuse  */
			*next;
} tile_struct;

typedef struct tile_spine_struct
{
    short length;
    struct tile_struct *front, *back;
    struct tile_spine_struct *direction[2],   /* UP (larger lengths) or DOWN */
                             *chain;
} tile_spine_struct;


typedef struct hash_struct
{
    unsigned long hashval;
    short  startpos;
    struct hash_struct  *next_bucket,	/* IE with same hashvalue  */
			*chain;		/* next hash-struct in list */
    struct hash_table_struct *tablepos;	/* position in table - speed resetting of table */
}  hash_struct;

typedef struct hash_table_struct
{
    struct hash_struct *front, *back;	/* FIFO of text strings with same KR-hash value */
} hash_table_struct;


FILE *Y_SUMMARY;
FILE *Y_SUBMISSIONS;
FILE *Y_NEWFILES;
FILE *Y_STATUS;
FILE *Y_NUMBERS;
filename newfiles[MAX_NO_FILES];
filename oldfiles[MAX_NO_FILES];
filename new_basename[MAX_NO_FILES];
filename old_basename[MAX_NO_FILES];

word_struct Text[MAXFILE],
	   Patn[MAXFILE];
short start_patn,			/* First non-marked element of pattern */
      start_text,			/* First non-marked element of text */
      patn_sentinel,			/* dummy end of string element (marked at the outset) */
      text_sentinel;
unsigned int length_of_text,
             length_of_pattern,
	     min_string_length;	/* String length below which matching not "worthwhile" */
hash_table_struct hash_table[HASH_TABLE_SIZE];
hash_struct  head_of_hash_list;
tile_struct  tile_free_list;
tile_spine_struct  tile_spine_free_list;
unsigned long hash_powers[MAXFILE];	/* hashed powers of KR_MULT (saves recomputation) */

struct Results_type
{
	char *sort_command;
	long Result_number;
	long aim_number;
} Results;

/* copys and strips trailing newline to produce newstr and
   generates basename in third arg */
void stcp(char *newstr,char *oldstr,char *basename)
{
    int counter1 = 0;
    int counter2 = 0;
    int counter3 = 0;

    while ((oldstr[counter1] != '\0') && (counter1 < MAX_FILE_NAME))
    {
	if (oldstr[counter1] != '\n')
	{
	    newstr[counter2++] = oldstr[counter1];
	    basename[counter3++] = oldstr[counter1];
	    if (newstr[counter2 - 1] == '/')
		counter3 = 0;
	}
	counter1++;
    }
    newstr[counter2] = '\0';
    basename[counter3] = '\0';
}

#ifdef DEBUG
void print_arrays()
{
    register int i;

    printf("\nstart_patn: %d, patn_sentinel(prev): %d, start_text: %d, text_sentinel(prev): %d\n",start_patn, Patn[patn_sentinel].prev,
			start_text, Text[text_sentinel].prev);
    for(i = 0; i <= length_of_pattern; i++)
	if(marked(Patn[i]))
	    printf("*** Patn[%d] Value: %d Next: %d, Prev: %d, End: %d\n",i,Patn[i].value, Patn[i].next, Patn[i].prev, Patn[i].end);
	else
	    printf("    Patn[%d] Value: %d Next: %d, Prev: %d, End: %d\n",i,Patn[i].value, Patn[i].next, Patn[i].prev, Patn[i].end);
    for(i = 0; i <= length_of_text; i++)
	if(marked(Text[i]))
	    printf("*** Text[%d] Value: %d Next: %d, Prev: %d, End: %d\n",i,Text[i].value, Text[i].next, Text[i].prev, Text[i].end);
	else
	    printf("    Text[%d] Value: %d Next: %d, Prev: %d, End: %d\n",i,Text[i].value, Text[i].next, Text[i].prev, Text[i].end);
}
#endif

FILE *open_file(char *file_name,char *type)
{
	FILE *temp_ptr;
#ifdef DEBUG
	fprintf(stderr, "Opening file %s\n", *file_name);
#endif
	if ((temp_ptr = fopen(file_name,type)) == NULL)
	{
		(void)fprintf(stderr,"could not open file %s\n",file_name);
		exit(1);
	}
	return(temp_ptr);
}

boolean init(char *fname1, char *fname2, word_struct *Text, word_struct *Patn)
{
    FILE *file1, *file2, *tempfile;
    register int i;
    int prev_instance[VOCAB_LENGTH];
    register word_struct *Textpt = Text;
    register word_struct *Patnpt = Patn;

    file1 = open_file(fname1, "r");
    file2 = open_file(fname2, "r");

    fscanf(file1, "%d", &length_of_pattern);	/* It is assumed first item in file is its length (without this item!) */
    fscanf(file2, "%d", &length_of_text);

    if(length_of_pattern <= min_string_length || length_of_text <= min_string_length)
	{
/*
	if(length_of_pattern <= min_string_length)
	    fprintf(stderr, "Pattern file %s (%d) is less that the minimum length %d\n", fname1, length_of_pattern, min_string_length);
	if(length_of_text <= min_string_length)
	    fprintf(stderr, "Text file %s (%d) is less that the minimum length %d\n", fname2, length_of_text, min_string_length);
*/
	fclose(file1); fclose(file2);
	return FALSE;
	}

    if(length_of_text > MAXFILE || length_of_pattern > MAXFILE )
	{
	fprintf(stderr, "One of the token files is too long\n");
	fclose(file1); fclose(file2);
	return FALSE;
	}

    /* In new versions, pattern is longer and is hashed by scanpattern, rather
	then text */
    if(length_of_pattern < length_of_text)
	{
	tempfile = file1; file1 = file2; file2 = tempfile;
	i = length_of_pattern;
	length_of_pattern = length_of_text;
	length_of_text = i;

#ifdef DEBUG
	fprintf(stderr, "pattern (%d): %s text(%d): %s\n",length_of_pattern, fname2, length_of_text, fname1);
	fflush(stderr);
#endif

	}

#ifdef DEBUG
    else
	{
	fprintf(stderr, "pattern (%d): %s text(%d): %s\n",length_of_pattern, fname1, length_of_text, fname2);
	fflush(stderr);
	}
#endif


    /* Reading in pattern - i.e. shorter - file */

    i = 1;
    start_patn = 0;
    fscanf(file1, "%hd", &((*Patnpt).value));
    (*Patnpt).end = MARK;
    (*(Patnpt++)).prev = MARK;

    while(fscanf(file1, "%hd", &((*Patnpt).value)) != EOF)
	{
	(*Patnpt).prev = i - 1;
	(*Patnpt).end = MARK;
	(*(Patnpt-1)).next = i++;
	Patnpt++;
	}
    patn_sentinel = i;
    (*(Patnpt-1)).next = i;
    (*Patnpt).value = (*Patnpt).next = (*Patnpt).end = MARK;
    (*Patnpt).prev = i - 1;	/* sentinel points to last unmarked element */


    /* Reading in text */

    i = 1;
    start_text = 0;
    fscanf(file2, "%hd", &((*Textpt).value));
    (*Textpt).end = MARK;
    (*(Textpt++)).prev = MARK;
    hash_powers[0] = KR_MULT;

    while(fscanf(file2, "%hd", &((*Textpt).value)) != EOF)
	{
	hash_powers[i] = hash_powers[i-1] * KR_MULT;
	(*Textpt).prev = i - 1;
	(*Textpt).end = MARK;
	(*(Textpt-1)).next = i++;
	Textpt++;
	}
    text_sentinel = i;
    (*(Textpt-1)).next = i;
    (*Textpt).value = (*Textpt).next = (*Textpt).end = MARK;
    (*Textpt).prev = i - 1;

#ifdef DEBUG
    print_arrays() ;
#endif

    fclose(file1); fclose(file2);
    return TRUE;
}

hash_struct *add_to_hash_table(unsigned long hashval, short startpos, hash_struct *hpt)
{
    hash_struct *new;
    hash_table_struct *tabpt;


    hpt -> hashval = hashval;
    hpt -> startpos = startpos;
    hpt -> next_bucket = NULL;
    tabpt = &(hash_table[hashval % HASH_TABLE_SIZE]);
    if((*tabpt).back == NULL)
	(*tabpt).back = (*tabpt).front = hpt;
    else
	{
	(*tabpt).front -> next_bucket = hpt;
	(*tabpt).front = hpt;
	}
    hpt -> tablepos = tabpt;
    if (hpt -> chain != NULL)
	{
	hpt = hpt -> chain;
	}
    else
	{
	new = (hash_struct *) malloc (sizeof(hash_struct));
	new -> chain = NULL;
	hpt -> chain = new;
	hpt = new;
	}
    return(hpt);
}

#ifdef DEBUG
void print_tile_lists(register tile_spine_struct *tspt)
{
    register tile_struct *tpt;
    register int i;

    for( ; tspt != NULL; tspt = tspt -> direction[DOWN])
	{
	fprintf(stderr,"Length %d\t:",tspt -> length);
	for(tpt = tspt -> back, i = 1; tpt != NULL; tpt = tpt -> next, i++)
	    {
	    fprintf(stderr,"(%d-%d, %d-%d)  ",tpt -> start_patn, tpt -> end_patn, tpt -> start_text, tpt -> end_text);
	    if(i % 4 == 0)
		fprintf(stderr,"\n\t\t");
	    }
	    fprintf(stderr,"\n");
	}
    fprintf(stderr,"\n");
}
#endif

/* start fresh list for new (putative) tile-length */

tile_spine_struct *set_new_vertebra(tile_spine_struct **spine_free_list, tile_struct *new_item, unsigned short length)
{
    register tile_spine_struct *new_free,
				*new_vert = *spine_free_list;

    new_vert -> length = length;
    new_vert -> front = new_vert -> back = new_item;
    new_vert -> direction[DOWN] = new_vert -> direction[UP] = NULL;
    if(new_vert -> chain != NULL)
	*spine_free_list = new_vert -> chain;
    else
	{
	new_free = (tile_spine_struct *) malloc(sizeof(tile_spine_struct));
	new_free -> chain = NULL;
	(*spine_free_list) -> chain = new_free;
	(*spine_free_list) = new_free;
	}
    return(new_vert);
}

/* find the correct vertebra for the length of new tile (or add vert) and add new tile to its list */

void add_putative_tile(tile_struct *new_item, tile_spine_struct **cur_list, tile_spine_struct **first_list,
						tile_spine_struct **spine_free_list)
{
    register short length = new_item -> end_patn - new_item -> start_patn + 1;
    register tile_spine_struct *tspt;
    register short dir;		/* either UP or DOWN - used when looking for length-list */


    if(*first_list == NULL)
	{
	*cur_list = *first_list = set_new_vertebra(spine_free_list, new_item, length);
	}
    else if (length == (*cur_list) -> length)	/* extend current list */
	{
	(*cur_list) -> front -> next = new_item;
	(*cur_list) -> front = new_item;
	}
    else
	{
	dir = length > (*cur_list) -> length ? UP : DOWN;
	for(tspt = *cur_list; tspt -> direction[dir] != NULL; tspt = tspt -> direction[dir])
	    {
	    if(dir == UP)
		{
		if(tspt -> direction[UP] -> length >= length)
		    break;
		}
	    else
		{
		if(tspt -> direction[DOWN] -> length <= length)
		    break;
		}
	    }
	if(tspt -> direction[dir] != NULL && tspt -> direction[dir] -> length == length)
	    {
	    (*cur_list) = tspt -> direction[dir];
	    (*cur_list) -> front -> next = new_item;
	    (*cur_list) -> front = new_item;
	    }
	else
	    {
	    (*cur_list) = set_new_vertebra(spine_free_list, new_item, length);
	    (*cur_list) -> direction[dir] = tspt -> direction[dir];
	    tspt -> direction[dir] = *cur_list;
	    (*cur_list) -> direction[(dir + 1) % 2] = tspt;	/* fix pointer in reverse direction */
	    if((*cur_list) ->  direction[dir] == NULL)	/* New top or bottom node */
		{
		if((*cur_list) -> length > (*first_list) -> length)	/* I.E. new first list */
		    *first_list = *cur_list;
		}
	    else	/* new intermediate node */
		(*cur_list) ->  direction[dir] -> direction[(dir + 1) % 2] = *cur_list;
	    }
	}
}

tile_spine_struct *scanpattern (int matchsize, int *very_long_string, tile_spine_struct **spine_free_list)
{
    register  short  i, j, k, p, t;
    register unsigned long hashval,
			   power = hash_powers[matchsize - 1];
    hash_struct *hpt = &head_of_hash_list;
    register hash_struct *probe;
    tile_struct *tfpt = &tile_free_list,
			  *new_tile;
    tile_spine_struct *cur_list = NULL, *first_list = NULL;
    hash_struct *h;

    /* KR hash all (non-marked) text strings, matchsize in lenght */


    i = start_text;
    while ((k = i + matchsize - 1) <= Text[text_sentinel].prev)
	{
	if (marked(Text[k]))
	    {
	    i = Text[Text[k].prev].next;
	    }
	else
	    {
	    /*  hash the start of the string (less than matchsize items) - pump priming */
	    hashval = Text[i].value;
	    for(j = i+1; j <= k; j++)
		hashval = hashval * KR_MULT + Text[j].value;

	    hpt = add_to_hash_table(hashval, i, hpt);	   /* string exactly matchsize in length */
	    /* j == i + matchsize . i is original. Note that sentinel is MARK'd, so cannot run off end */
	    while(unmarked(Text[j]))
		{
		hashval = hashval * KR_MULT + Text[j++].value - power * Text[i++].value;
		hpt = add_to_hash_table(hashval, i, hpt);
		}
	    i++;	/* i is j - matchsize so need to restore proper interval */
	    }
	}

#ifdef DEBUG
    for(i=0; i < HASH_TABLE_SIZE; i++)
	if (hash_table[i].back != NULL)
	    {
	    printf("hash_tab[%d]: ", i);
	    for(h=hash_table[i].back; h != NULL; h = h -> next_bucket)
		printf("%d/%u  ",h -> startpos, h -> hashval);
	    printf("\n");
	    }
#endif


     /* Now KR hash each pattern string of suitable size and test against hashed text stings */

    i = start_patn;
    while ((k = i + matchsize - 1) <= Patn[patn_sentinel].prev)
	{
	if (marked(Patn[k]))
	    {
	    i = Patn[Patn[k].prev].next;
	    }
	else
	    {
	    /*  hash the start of the string (less than matchsize items) - pump priming */
	    hashval = Patn[i].value;
	    for(j = i+1; j <= k; j++)
		hashval = hashval * KR_MULT + Patn[j].value;

	    j--;
	    /* j == i + matchsize - 1. Note that sentinel is MARK'd, so cannot run off end */
	    while(unmarked(Patn[j]))
		{
		probe = hash_table[hashval % HASH_TABLE_SIZE].back;
		while (probe != NULL)
		    {
		    if (probe -> hashval == hashval)
			{
			t = probe -> startpos + matchsize;		/* Try to extend match */
			p = j + 1;
			while (unmarked(Patn[p]) && unmarked(Text[t]) && Patn[p].value == Text[t].value)
			    {
			    p++; t++;
			    }

			if(p - i > *very_long_string)
			    {
			    fprintf(stderr, "Very long string of length %d found\n", p - i);
			    *very_long_string = p - i;
			    /* still have to this this before leaving reset text hash-table  */
			    hpt = &head_of_hash_list;
			    while(hpt -> chain != NULL)
			        {
			        (*(hpt -> tablepos)).back = NULL;
			        hpt = hpt -> chain;
			        }
			    return(NULL);
			    }


			/*  Store new match. First use next element on match free list */
			tfpt -> start_patn = i;
			tfpt -> end_patn = p - 1;;
			tfpt -> start_text = probe -> startpos;
			tfpt -> end_text = t - 1;
			tfpt -> next = NULL;		/* In case where markarray not called in previous iteration
							   due to very_long_string, and item still points to something */


			/* Push the new item onto the list of lists (max length at top) */

			add_putative_tile(tfpt, &cur_list,&first_list, spine_free_list);

			/* Bump match free-list to new item, or create one if at the end of the match free-list */
			if (tfpt -> chain != NULL)
			    {
			    tfpt = tfpt -> chain;
			    }
			else
			    {
			    new_tile = (tile_struct *) malloc (sizeof(tile_struct));
			    new_tile -> chain = NULL;
			    tfpt -> chain = new_tile;
			    tfpt = new_tile;
			    }
			}
		    probe = probe -> next_bucket;
		    }
		hashval = hashval * KR_MULT + Patn[++j].value - power * Patn[i++].value;
		}
	    }
	}
    /* reset text hash-table  */
    hpt = &head_of_hash_list;
    while(hpt -> chain != NULL)
	{
	(*(hpt -> tablepos)).back = NULL;
	hpt = hpt -> chain;
	}
    return(first_list);
}

/* Given a list of putative-tile lists, and a pointer to the tile currently under examination, return next */
tile_struct *next_putative_tile(tile_spine_struct **spine_list)
{
    tile_struct *hold;

    if((*spine_list) -> back == NULL)
	{
	if((*spine_list = (*spine_list) -> direction[DOWN]) == NULL)  /* just finished bottom (smallest length) list */
	    return(NULL);
	}

    hold = (*spine_list) -> back;
    (*spine_list) -> back = (*spine_list) -> back -> next;
    hold -> next = NULL;
    return(hold);
}


/* Given the set of matches organized as a list of lists ordered from the largest match down
   mark the Text and Patn arrays iff no element in the range of a
   match is already marked (Would not have been marked initially, but may happen
   now if new matches overlap). Returns the new count of marked tokens and the number of tiles */

void markarrays(tile_spine_struct *putative_tiles, int *n_marked, int nlow_tiles[], int matchsize, tile_spine_struct ** spine_free_list)
{
    register int i, j, next, length, incr;
    register  word_struct *Textpt, *t, *Patnpt, *p;
    register tile_struct *cur_tile;
    int Patnprev, Textprev, diffs, diffe;
    tile_spine_struct *dummy_cur_list;

    while(( cur_tile = next_putative_tile(&putative_tiles)) != NULL)
	{
	Textpt = &Text[cur_tile -> start_text];
	Patnpt = &Patn[cur_tile -> start_patn];
	length = putative_tiles -> length;
#ifdef DEBUG
fprintf(stderr, "Looking at Patn: %d-%d Text: %d-%d Size: %d\n",cur_tile -> start_patn, cur_tile -> end_patn, cur_tile -> start_text, cur_tile ->  end_text, length );
#endif
	incr = length - 1;
	Patnprev = (*Patnpt).prev;
	Textprev = (*Textpt).prev;

	/* Text could have been marked for that range by sibling match */

	if(unmarked(*Textpt) && unmarked(*(Textpt + incr)) && unmarked(*Patnpt) && unmarked(*(Patnpt + incr)))
	    {

#ifdef DISPLAY_TILES
printf("Marking Patn: %d-%d Text: %d-%d Size: %d\n",cur_tile -> start_patn, cur_tile -> end_patn, cur_tile -> start_text, cur_tile -> end_text, length );
#endif
	    /* Check now that match is genuine rather than hash artefact */
	    for(p=Patnpt, t=Textpt, j = length; j > 0; p++, t++, j--)
		{
		if ((*p).value != (*t).value)	/* not a genuine match */
		    break;
		}
	    if(j > 0)
		{
#ifdef DEBUG
printf("KR HASH match proven false\n");
#endif
		continue;
		}
	    next = (*(Patnpt + incr)).next;
	    if(cur_tile -> start_patn == start_patn)	/* Is the start of the pattern-match the start of the pattern ?*/
		{
		start_patn = next;
		Patn[start_patn].prev = MARK;
		}
	    else
		{
		Patn[next].prev = Patnprev;	/* This also works for patn_sentinel (shifts pointer to it forward) */
		Patn[ Patnprev ].next = next;
		}
	    next = (*(Textpt + incr)).next;
	    if(cur_tile -> start_text == start_text)	/* Ditto for text  */
		{
		start_text = next;
		Text[start_text].prev = MARK;
		}
	    else
		{
		Text[next].prev = Textprev;
		Text[ Textprev ].next = next;
		}
	    for(j = length ; j > 0; j--)
		{
		(*Patnpt).prev = Patnprev;
		(*Textpt).prev = Textprev;
		(*Patnpt).end = cur_tile -> end_patn;
		(*Textpt).end = cur_tile -> end_text;
		(*Patnpt).value = -(*Patnpt).value;
		(*Textpt).value = -(*Textpt).value;
		(*(Patnpt++)).next = cur_tile -> start_text;
		(*(Textpt++)).next = cur_tile -> start_patn;
		}
	    *n_marked += length;
	    if( length < min_string_length + 3)
		nlow_tiles[length - min_string_length] += length;   /* Count of 3 smallest sizes */
	    else
		nlow_tiles[3] += length; /* Count of other tile sizes recorded here */
	    }
	else		/* can the forshortened string be reused? */
	    {
	    if((*Patnpt).prev == (*(Patnpt + incr)).prev)
		{
		/* printf("Pattern string completely occluded\n"); */
		continue;
		}
	    if((*Textpt).prev == (*(Textpt + incr)).prev)
		{
		/* printf("Text string completely occluded\n");  */
		continue;
		}
	    i = unmarked(*Patnpt) ? 0 :  (*Patnpt).end - cur_tile -> start_patn + 1;
	    j = unmarked(*Textpt) ? 0 :  (*Textpt).end - cur_tile -> start_text + 1;
	    diffs = (i >= j) ? i : j;
	    i = unmarked(*(Patnpt + incr)) ? 0 : cur_tile -> end_patn - (*(Patnpt + incr)).prev;
	    j = unmarked(*(Textpt + incr)) ? 0 : cur_tile -> end_text - (*(Textpt + incr)).prev;
	    diffe = (i >= j) ? i : j;
	    if((int) length - diffs - diffe >= matchsize)   /* string still viable */
		{
		cur_tile -> start_patn += diffs;
		cur_tile -> start_text += diffs;
		cur_tile -> end_patn -= diffe;
		cur_tile -> end_text -= diffe;
		dummy_cur_list = putative_tiles;
		add_putative_tile(cur_tile, &dummy_cur_list, &putative_tiles, spine_free_list);
		}
	    }
	}
}

void rkr_gst(int *n_marked, int nlow_tiles[])
{
    tile_spine_struct *putative_tiles, *spine_free_list;
    int n_matches, very_long_string, prev_matchsize, matchsize = 20;


    prev_matchsize = 2 * matchsize;
    for(;;)
	{
	spine_free_list = &tile_spine_free_list;
	very_long_string = prev_matchsize;
	putative_tiles = scanpattern(matchsize, &very_long_string, &spine_free_list);

#ifdef DEBUG
     fprintf(stderr, "Heap After scanning for matchsize %d:\n", matchsize);
     print_tile_lists(putative_tiles);
#endif

	if(putative_tiles != NULL)
	    markarrays(putative_tiles, n_marked, nlow_tiles, matchsize, &spine_free_list);
	if(very_long_string > prev_matchsize)	/* VERY long string found; retry with larger string */
	    {
	    matchsize = very_long_string;
	    prev_matchsize = 2 * matchsize;
	    }
	else
	    {
	    prev_matchsize = matchsize;
	    if(matchsize != min_string_length)	/* from previous iteration! */
		matchsize = (matchsize <= 2 * min_string_length) ? min_string_length : matchsize / 2;
	    else
		break;
	    }
	}

}

void compare_a_pair(char *file1, char *file2)
{
    int n_marked = 0, nlow_tiles[4];
    register double weighted_ntiles = 0.0, incr = 0.25;
    register int i;
    double percentmatch;

    for(i=0; i<4; i++)
	nlow_tiles[i] = 0;

    if( ! init(file1,file2, Text, Patn))
	return;

    rkr_gst(&n_marked, nlow_tiles);

     for(i=0; i <=2; i++)
	{
	weighted_ntiles += nlow_tiles[i] * incr;
	incr += 0.25;
	}
     weighted_ntiles += nlow_tiles[3];
     percentmatch =  (n_marked == 0) ? 0.0 : 100.0 * n_marked / length_of_pattern;
     /* percentmatch =  (n_marked == 0) ? 0.0 : 100.0 * weighted_ntiles / length_of_pattern; */

#ifdef DEBUG
     printf("Number of marked lines %d / %d (%5.2f%%) in %d tiles\n", n_marked, length_of_pattern, ((double) 100 * n_marked / length_of_pattern), n_marked);
      for(i=0; i <=2; i++)
	printf("low-tiles[%d]: %d  ",i + min_string_length, nlow_tiles[i]);
     printf("other-tiles[rest]: %d\n",nlow_tiles[3]);

     printf("Weighted sig_tiles %5.2f, ", weighted_ntiles);
     if(n_marked > 0)
	printf("Weighted PC sig_tiles/tiles %5.2f%%,\nCombined Weighted PC sig_tiles/tiles - PC match %5.2f%%\n",
	    100 * weighted_ntiles / n_marked, percentmatch);
    else
	printf("Weighted PC sig_tiles/tiles 0%%,\nCombined Weighted PC sig_tiles/tiles - PC match 0%%\n");
#endif

    (void)fprintf(Y_NUMBERS,"%5.2f\n",percentmatch);

    Results.Result_number++;
    if (Results.Result_number >= 5*Results.aim_number)  /* sorts and chops when file is 5 * that required */
    {
	(void)fclose(Y_SUMMARY); /* if you don't close and open the file, it doesn't work... */

	(void)system(Results.sort_command);     /* sort results, and chop off bottom */
	Results.Result_number = 0;

	if ((Y_SUMMARY = fopen("yap.summary","a")) == NULL)
	{
	    (void)fprintf(stderr,"could not open file yap.summary");
	    exit(1);
	}


    }

    fprintf(Y_SUMMARY,"%s  %s  %5.2f\n",file1,file2,percentmatch);
}

int main(int argc,char *argv[])
{
    register int oldcounter, newcounter, newnum;
    int No_new = 0, No_old = 0;
    filename fname;

    if (argc < 4 || argc > 5)
    	{
	(void)fprintf(stderr,"Usage: %s [Min_String_Length] <sort command string> <No. files already tested> <target number>\n",argv[0]);
	exit(1);
    	}

    min_string_length = (argc == 5) ? strtol(argv[1], NULL, 10) : MIN_STRING;
    Results.sort_command = argv[argc -3];
    newnum = atoi(argv[argc -2]);
    Results.aim_number = atoi(argv[argc -1]);
    Results.Result_number = 0;
    Y_SUMMARY = open_file("yap.summary","a");
    Y_SUBMISSIONS = open_file("yap.submissions","r");
    Y_NEWFILES = open_file("yap.newfiles","r");
    Y_STATUS = open_file("yap.status","a");
    Y_NUMBERS = open_file("yap.numbers","a");
    head_of_hash_list.chain = head_of_hash_list.next_bucket = NULL;
    tile_free_list.chain = NULL;
    tile_spine_free_list.chain = NULL;
    for(newcounter=0; newcounter < HASH_TABLE_SIZE; newcounter++)
	hash_table[newcounter].front = hash_table[newcounter].back = NULL;



    while (fgets(fname,MAX_FILE_NAME,Y_NEWFILES) && (No_new < MAX_NO_FILES)) {
        stcp(newfiles[No_new],fname,new_basename[No_new]);
        No_new++;
    }
    while (fgets(fname,MAX_FILE_NAME,Y_SUBMISSIONS) && (No_old < MAX_NO_FILES)) {
        stcp(oldfiles[No_old],fname,old_basename[No_old]);
        No_old++;
    }
    if ((No_new >= MAX_NO_FILES) || (No_old >= MAX_NO_FILES))
	(void)fprintf(stderr,"WARNING: too many submissions\n");

    if (! Results.aim_number)
	Results.aim_number = 2*No_old;

    for (newcounter = 0 ; newcounter < No_new ; newcounter++)
    {
	newnum++;
	(void)fprintf(Y_STATUS,"%d: %s\n",newnum,newfiles[newcounter]);
	fflush(Y_STATUS);
	for (oldcounter = No_old - 1 ; oldcounter >= 0 ; oldcounter--)
	    {
	    if (oldcounter < newcounter)
		break;

	    if (! strncmp(new_basename[newcounter],old_basename[oldcounter],MAX_FILE_NAME))
		continue;	     /* in case someone has a submission in more than one category. */
	    compare_a_pair(newfiles[newcounter],oldfiles[oldcounter]);
	}
    }



    (void)fclose(Y_NEWFILES);
    (void)fclose(Y_SUBMISSIONS);
    (void)fclose(Y_STATUS);
    (void)fclose(Y_SUMMARY);
    (void)fclose(Y_NUMBERS);

    (void)system(Results.sort_command);   /* final sort and cut-off */
    return(0);
}
